//
// Created by xili on 2024/8/27 16:41.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    string removeKdigits(string num, int k) {
        stack<char> s;
        for (char item: num) {
            // 在k大于0并且栈不为空的情况下，弹出栈顶元素，直到找到比当前元素小的数字
            while (k > 0 && !s.empty() && s.top() > item) {
                s.pop();
                k--;
            }
            // 将当前数字压入栈，如果栈为空时跳过前导零
            if (!s.empty() || item != '0') {
                s.push(item);
            }
        }
        // 如果还有剩余的k，需要继续弹出栈顶元素
        while (k > 0 && !s.empty()) {
            s.pop();
            k--;
        }
        // 构建结果字符串
        string ans;
        while (!s.empty()) {
            ans.push_back(s.top());
            s.pop();
        }
        // 由于栈是LIFO，需要反转字符串
        reverse(ans.begin(), ans.end());
        // 如果最终结果为空，返回 "0"
        return ans.empty() ? "0" : ans;
    }
};
